#include <vector>
using namespace std;
class Solution1
{
    //回溯法,时间超时
public:
    int N = __INT16_MAX__;
    void jumpH(int position, vector<int> &nums, int i)
    {
        if (position == nums.size() - 1)
        {
            N = min(N, i);
        }
        int can = position + nums[position];
        int large = nums.size() - 1;
        int featureJump = min(can, large);
        for (int j = position + 1; j <= featureJump; j++)
        {
            jumpH(j, nums, i + 1);
        }
    }
    int jump(vector<int> &nums)
    {
        jumpH(0, nums, 0);
        if (N == __INT16_MAX__)
        {
            return 0;
        }
        return N;
    }
};

class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int max_p = 0;
        int end = 0;
        int steps = 0;
        for(int i = 0;i<nums.size()-1;i++){
            max_p = max(max_p,i+nums[i]);
            if(i==end){
               end = max_p;
               steps++;
            }
        }
        return steps;
    }
};